package graph;

import java.util.*;

/**
 * Dijkstra（迪杰斯特拉算法）未使用二叉堆优化的版本
 * 算法时间复杂度为 O(n^2)
 * 支持获取源点到目标点的最短路径
 */
public class DijkstraPathNormal_1117 {

    /**
     * 获取源点到目标点的最短路径
     *
     * @param source 源点
     * @param target 目标点
     */
    public static List<Edge<Integer>> dijkstra(Node<Integer> source, Node<Integer> target) {
        // 存储源点到任意节点的最短距离
        Map<Node<Integer>, Integer> distanceMap = new HashMap<>();
        // 存储已经确定最短距离的点
        Set<Node<Integer>> markNodes = new HashSet<>();
        // 记录距离自己最近的父节点
        Map<Node<Integer>, Node<Integer>> parentMap = new HashMap<>();
        // 初始化源点到自己的最短距离
        distanceMap.put(source, 0);

        // 获取没有确定最短距离且距离源点最近的点
        Node<Integer> minNode = getUnmarkMinDistanceNode(distanceMap, markNodes);
        while (null != minNode) {
            Integer distance = distanceMap.get(minNode);
            for (Edge<Integer> edge : minNode.nextEdges) {
                // 经过当前边到达edge.to节点的距离
                int newDistance = distance + edge.weight;
                // 已知源点到edge.to节点的最短路径
                Integer oldDistance = distanceMap.getOrDefault(edge.to, Integer.MAX_VALUE);
                if (newDistance < oldDistance) {
                    // 经过当前边的距离更近就更新距离表
                    distanceMap.put(edge.to, newDistance);
                    // 记录源点到edge.to节点的最短路径中，edge.to节点的父节点
                    parentMap.put(edge.to, minNode);
                }
            }
            if (Objects.equals(minNode, target)) {
                // 如果已经找到源点到目标点的最短路劲就停止循环
                break;
            }
            markNodes.add(minNode);
            minNode = getUnmarkMinDistanceNode(distanceMap, markNodes);
        }

        if (!parentMap.containsKey(target)) {
            // 源点到目标点不可达
            return Collections.emptyList();
        }

        List<Edge<Integer>> result = new ArrayList<>();
        Node<Integer> node = target;
        Node<Integer> parent;
        // 回溯整条路径
        do {
            parent = parentMap.get(node);
            int distance = distanceMap.get(node) - distanceMap.get(parent);
            result.add(new Edge<>(distance, parent, node));
            node = parent;
        } while (source != parent);
        Collections.reverse(result);
        return result;
    }

    /**
     * 获取没有确定最短距离且距离源点最近的点
     * 由于整个distanceMap，随着循环distanceMap中节点会越来越多，取决于点数，因此该方法的时间复杂度为 O(n)
     *
     * @param distanceMap 距离表
     * @param markNodes   确定距离的点
     */
    private static Node<Integer> getUnmarkMinDistanceNode(Map<Node<Integer>, Integer> distanceMap, Set<Node<Integer>> markNodes) {
        Node<Integer> minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for (Map.Entry<Node<Integer>, Integer> entry : distanceMap.entrySet()) {
            if (!markNodes.contains(entry.getKey()) && entry.getValue() < minDistance) {
                minNode = entry.getKey();
                minDistance = entry.getValue();
            }
        }
        return minNode;
    }
}
